/*
 * Código-Fonte escrito com base no livro Projeto de Algoritmos, do autor
 * Nivio Ziviani
 */
package exerciciosGrafos;

import cap7.listaadj.autoreferencia.Grafo; // vide Programa 7.3

public class VerificarGrafoAciclico {
    public static final byte branco = 0;
    public static byte cinza        = 1;
    public static byte preto        = 2;
    private int d[], t[], antecessor[];
    private Grafo grafo;
    public static boolean aciclico = true;
    
    public VerificarGrafoAciclico( Grafo grafo ) {
        this.grafo = grafo;
        int n = this.grafo.numVertices();
        
        d = new int[ n ];
        t = new int[ n ];
        antecessor = new int[ n ];
    }
    
    private int visitaDfs( int u, int tempo, int cor[] ) {
        cor[ u ] = cinza;
        this.d[ u ] = ++tempo;
        
        if( !this.grafo.listaAdjVazia( u ) ) {
            Grafo.Aresta a = this.grafo.primeiroListaAdj( u );
            
            while( a != null ) {
                int v = a.v2();
                
                if( cor[ v ] == cinza ) {
                    aciclico = false;
                }
                
                if( cor[ v ] == branco ) {
                    this.antecessor[ v ] = u;
                    tempo = this.visitaDfs( v, tempo, cor );
                }
                
                a = this.grafo.proxAdj( u );
            }
        }
        
        cor[ u ] = preto;
        this.t[ u ] = ++tempo;
        
        return tempo;
    }
    
    public void buscaEmProfundidade() {
        int tempo = 0;
        int cor[] = new int[ this.grafo.numVertices() ];
        
        for( int u = 0; u < grafo.numVertices(); u++ ) {
            cor[ u ] = branco;
            this.antecessor[ u ] = -1;
        }
        
        for( int u = 0; u < grafo.numVertices(); u++ ) {
            if( cor[ u ] == branco ) {
                tempo = this.visitaDfs( u, tempo, cor );
            }
        }
    }
    
    public int d( int v ) {
        return this.d[ v ];
    }
    
    public int t( int v ) {
        return this.t[ v ];
    }
    
    public int antecessor( int v ) {
        return this.antecessor[ v ];
    }
}
